1. Field of the Invention
The present invention relates to computer systems and methods in which data resources are shared among concurrent data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the invention concerns an implementation of a mutual exclusion mechanism known as “read-copy update” in a preemptive real-time computing environment.
2. Description of the Prior Art
By way of background, read-copy update is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to multiprocessor computing environments in which the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where read-side lock acquisition would be quite burdensome.
The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of operations that may be currently referencing the data. The other view is the new (post-update) data state that is available for the benefit of operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that all executing operations will no longer maintain references to the pre-update data. The second-phase update operation typically comprises freeing a stale data element. In certain RCU implementations, the second-phase update operation may comprise something else, such as changing an operational state according to the first-phase update.
FIGS. 1A-1D illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables. Moreover, the list itself is a type of data structure.
It is assumed that the data element list of FIGS. 1A-1D is traversed (without locking) by multiple concurrent readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In FIG. 1A, the data element B is being referenced by a reader r1, as shown by the vertical arrow below the data element. In FIG. 1B, an updater u1 wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r1 is referencing it (which might crash r1), u1 preserves B while generating an updated version thereof (shown in FIG. 1C as data element B′) and inserting it into the linked list. This is done by u1 acquiring an appropriate lock (to synchronize with other updaters), allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the lock. All subsequent (post update) readers that traverse the linked list, such as the reader r2, will see the effect of the update operation by encountering B′. On the other hand, the old reader r1 will be unaffected because the original version of B and its pointer to C are retained. Although r1 will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays.
At some subsequent time following the update, r1 will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader is entitled to access B. It is at this point, representing expiration of the grace period referred to above, that u1 can free B, as shown in FIG. 1D.
FIGS. 2A-2C illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in FIG. 2A, a reader r1 is assumed be currently referencing B and an updater u1 wishes to delete B. As shown in FIG. 2B, the updater u1 updates the pointer from A to B so that A now points to C. In this way, r1 is not disturbed but a subsequent reader r2 sees the effect of the deletion. As shown in FIG. 2C, r1 will subsequently move its reference off of B, allowing B to be freed following expiration of the grace period.
In the context of the read-copy update mechanism, a grace period represents the point at which all running tasks (e.g., processes, threads, or other execution contexts) having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context switch, an idle loop, and user mode execution all represent quiescent states for any given CPU (as can other operations that will not be listed here).
In FIG. 3, four processes 0, 1, 2, and 3 running on four separate CPUs are shown to pass periodically through quiescent states (represented by the double vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four processes have passed through one quiescent state. If the four processes 0, 1, 2, and 3 were reader processes traversing the linked lists of FIGS. 1A-1D or FIGS. 2A-2C, none of these processes having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these processes would bypass B by following the links inserted by the updater.
There are various methods that may be used to implement a deferred data update following a grace period. One technique is to accumulate deferred update requests as callbacks (e.g., on callback lists), then perform batch callback processing at the end of the grace period. This represents asynchronous grace period processing. Updaters can perform first phase updates, issue callback requests, then resume operations with the knowledge that their callbacks will eventually be processed at the end of a grace period. Another commonly used technique is to have updaters perform first phase updates, block (wait) until a grace period has completed, and then resume to perform the deferred updates. This represents synchronous grace period processing.
Read-copy update has been used in production for many years in various operating system kernel environments, including the Linux® kernel. In non-preemptible kernels, grace period detection processing can be performed by observing natural quiescent states (e.g., context switch, user mode or idle loop) or by inducing such states (e.g., by forcing a context switch). In preemptible kernels, an executing RCU reader can be preempted by a higher priority task. Such preemption may occur even while the reader is in a kernel mode critical section referencing RCU-protected data elements. Although reader preemption represents a context switch, it may not be validly used for grace period detection. For that reason, RCU versions designed for preemptible environments (hereinafter “preemptible RCU”) do not rely on natural quiescent states. Instead, readers define their own quiescent states by registering and unregistering for RCU read-side critical section processing as they respectively enter and leave RCU read-side critical sections.
A technique used in existing versions of preemptible RCU for registering and unregistering readers for RCU read-side critical section processing is to provide a pair of per-processor counters and an index for identifying which counter of each pair is associated with a particular grace period. A reader registers for RCU read-side critical section processing by incrementing the currently indexed counter associated with the reader's processor. The reader then unregisters by decrementing the same indexed counter on the original processor, or on whatever processor the reader happens to be running when it exits the critical section. A modulo counting scheme may be used to determine when all of the counters indexed to a particular grace period have been collectively decremented to zero.
A grace period is determined to expire in a preemptible RCU environment when all readers that registered after the beginning of the grace period have subsequently unregistered. The grace period detection effort requires coordination with the various processors that may be running RCU readers. Readers need to know when the grace period detection logic commences new grace periods, and the grace period detection logic need to be certain that readers have exited their RCU read-side critical sections before declaring the end of old grace periods. Due in large part to CPU and/or compiler optimizations that allow memory accesses to be performed out of order, the coordination effort required for preemptible RCU grace period detection can be significant. For example, readers may have to implement atomic instructions, memory barriers and other high-overhead operations when registering and unregistering for RCU read-side critical section processing. One solution is to shift some of the reader overhead burden to the RCU grace period detection logic. This has been practiced in real-time versions of the Linux® kernel by using a state machine to coordinate grace period detection with the readers. However, there is still read-side overhead due to the reader registration/unregistration primitives each implementing interrupt disable/restore instructions. Moreover, the grace period latency imposed by the state machine is not insignificant.